package com.cat.dataStructure03;

import com.cat.binaryTree.ListNode;

import java.io.*;

/**
 * @author 曲大人的喵
 * @description https://www.luogu.com.cn/problem/P2880
 * @create 2025/11/17 20:41
 * @since JDK17
 */

public class Solution82 {
    static int n, q, MAXN = ((int) 5e4) + 10, LIMIT = 16;
    static int[] arr = new int[MAXN], log2 = new int[MAXN];
    static int[][] stmax = new int[MAXN][LIMIT], stmin = new int[MAXN][LIMIT];
    static int query(int l, int r) {
        int p = log2[r - l + 1];
        int a = Math.max(stmax[l][p], stmax[r - (1 << p) + 1][p]);
        int b = Math.min(stmin[l][p], stmin[r - (1 << p) + 1][p]);
        return a - b;
    }
    static void build() {
        log2[0] = -1;
        for (int i = 1; i <= n; i++) {
            log2[i] = log2[i >> 1] + 1;
            stmax[i][0] = arr[i];
            stmin[i][0] = arr[i];
        }
        for (int p = 1; p <= log2[n]; p++) {
            for (int i = 1; i + (1 << p) - 1 <= n; i++) {
                stmax[i][p] = Math.max(stmax[i][p - 1], stmax[i + (1 << (p - 1))][p - 1]);
                stmin[i][p] = Math.min(stmin[i][p - 1], stmin[i + (1 << (p - 1))][p - 1]);
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        n = ((int) in.nval);
        in.nextToken();
        q = ((int) in.nval);
        for (int i = 1; i <= n; i++) {  // 读入数据
            in.nextToken();
            arr[i] = ((int) in.nval);
        }
        build();
        for (int i = 0, l, r; i < q; i++) {
            in.nextToken();
            l = ((int) in.nval);
            in.nextToken();
            r = ((int) in.nval);
            out.println(query(l, r));
        }

        out.flush();
        out.close();
        br.close();
    }
}
